DP总结

背包 $\mathbf{DP}$

背包问题是最基础的 $DP$ 了,分为 $01$ 背包,完全背包和多重背包。

$\mathbf{01}$ 背包

$01$ 背包基本模型,背包的总体积为 $V$ ,总共有 $n$
件物体,每件物品的体积为 $v_i$ ,价值为 $w_i$
,每件物品只有一个,选择一个集合 $\mathbb{S}$ ,在满足
$\sum_{i\in \mathbb{S}} v_i\leq V$ 的前提下最大化
$\sum_{i\in \mathbb{S}} w_i$
。可以很快推得状态转移方程为:$dp[i]=\max(dp[i],dp[i-v[j]]+w[j])$
时间复杂度为 $\Theta(n^2)$ 。

完全背包

完全背包基本模型,背包的总体积为 $V$ ,总共有 $n$
件物体,每件物品的体积为 $v_i$,价值为 $w_i$
,每个物品有无限多个,选择一个集合 $\mathbb{S}$ ,在满足
$\sum_{i\in \mathbb{S}} v_i\leq V$ 的前提下最大化
$\sum_{i\in \mathbb{S}} w_i$ 。其实就是在 $01$
背包的基础上做了一点修改。 $01$
背包每件物品都只有一个,所有我们枚举物品时需要倒序枚举防止重复。完全背包允许重复,我们应该正序枚举。状态转移方程仍为:$dp[i]=\max(dp[i],dp[i-v[j]]+w[j])$
时间复杂度为 $\Theta(n^2)$ 。

多重背包

多重背包基本模型,背包的总体积为 $V$ ,总共有 $n$
件物体,每件物品的体积为 $v_i$ ,价值为 $w_i$ ,每个物品有 $n_i$
个,选择一个集合 $\mathbb{S}$ ,在满足
$\sum_{i\in \mathbb{S}} v_i\leq V$ 的前提下最大化
$\sum_{i\in \mathbb{S}} w_i$ 。考虑分解为 $01$ 背包,将每个物体拆分成
$n_i$ 个,再进行 $DP$ 。这样的时间复杂度为
$\Theta((\sum_{i=1}^n n_i)^2)$
。考虑优化。我们可以尽量少的进行拆分,使用二进制拆分将一种物品拆分为
$2^k (k=0,1,2 \cdots)$
个为一个新物品,这样可以满足取任意个,不影响答案。时间复杂度降低为
$\Theta((\sum_{i=1}^n \log_2 n_i)^2)$

分组背包

一般分组背包问题中,每组中只能选择一件物品。设 $dp[i][j]$ 代表前 $i$
组物品构成体积为 $j$ 的背包所能取得的最大价值和。状态转移方程易得
$dp[i][j]=\max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])$

树形 $\mathbf{DP}$

树形 $DP$ 的一般形式都是对子树的信息进行归并,其本质是 $dfs/bfs$
过程中的统计。有些时候,还会涉及组合等方面的知识。时间复杂度一般为
$\Theta(n)$ 。

区间 $\mathbf{DP}$

区间 $DP$ 的本质就是对区间信息的合并。在区间 $DP$
中,我们可以通过对区间信息的合并,解决一系列问题。

数位 $\mathbf{DP}$

数位 $DP$ 的一般形式是求出在给定区间 $[L,R]$ 内,符合条件 $f(i)$ 的数
$i$ 的个数。条件 $f(i)$
一般与数的大小无关,而与数的组成有关。一般使用记忆化搜索实现数位 $DP$
。从起点向下搜索,到最底层得到方案数,一层一层向上返回答案并累加,最后从搜索起点得到最终答案。一般来说,数位
$DP$ 解决区间 $[L,R]$ 的时候,会将其变成 $[0/1,R]-[0/1,L-1]$ 。

状态压缩 $\mathbf{DP}$

一般来说,使用状压 $DP$
是因为状态转移不得不使用到更加细节的信息,但如果细节信息单独储存又没有足够的空间,于是考虑用一个数表示一个状态,用这个数的二进制来储存细节信息。状压
$DP$ 需要大量的位运算技巧,现列举一些常用技巧:

  • 取出数字 $x$ 第 $i$ 位: $((x>>(i-1))\&1$ 。
  • 将数字 $x$ 第 $i$ 位取反: $x^{\land}=(1<<(i-1))$ 。
  • 将数字 $x$ 第 $i$ 位置 $1$ : $x|=(1<<(i-1))$ 。
  • 将数字 $x$ 第 $i$ 位置 $0$ : $x\&=(1<<(i-1))$ 。
  • 将数字 $x$ 最靠右的 $1$ 去掉: $x=x\&(x-1)$ 。
  • 取出数字 $x$ 最靠右的 $1$ : $x\&(-x)$ 。
  • 判断数字 $x$ 是否有两个连续的 $1$ : $if(x\&(x<<1))$ 。\
    一般来说,状压 $DP$ 数据范围在 $20$ 左右,可以用一个 $int$ 储存状态。

概率&期望 $\mathbf{DP}$

概率

概率亦称”或然率”。它反映随机事件出现的可能性大小。首先列举一些公式:
$P(\mathbb{S}-A)=1-P(A)$ $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ 定义如果
$A$ 发生,那么 $B$ 发生的概率为 $P(B|A)$ ,可以得到
$P(B|A)=\frac{P(A\cap B)}{P(A)}$ 假如有 $n$ 个事件 $B_1,B_2,B_3\cdots$
,且有 $\forall i,\forall j,B_i\cap B_j=\varnothing$
,$\bigcup_{i=1}^n B_i=\mathbb{S}$ ,那么有全概率公式
$P(A)=\sum_{i=1}^n P(B_i)\cdot P(A|B_i)$ 还有一个贝利叶公式
$P(B|A)=\frac{P(B)\cdot P(A|B)}{P(A)}$ 求概率是可以根据需要使用。

期望

数学期望,简称期望,是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小。期望的基本算法为
$E(x)=\sum_{i=1}^{\infty} x_i\cdot p_i$ 。期望具有可加性,即
$E(x+y)=E(x)+E(y)$ ,也有 $E(a\cdot x)=a\cdot E(x)$ 。在 $DP$ 时经常使用这一性质。

$\mathbf{DP}$ 优化

单调队列优化

单调队列是一种数据结构,通过双端队列实现在 $\Theta(1)$
的时间复杂度内获得区间最值。在许多转移方程带 $\max \min$ 的 $DP$
中,它可以很好地优化。

斜率优化

有一类问题,将n个物品分为连续的若干份,每分一次会通过一个计算方式产生一个代价,问代价最大/最小是多少。考虑
$DP$ ,容易想到状态转移方程为
$dp[i]=\min(\max)\left\{dp[j]+val(i,j)\right\}$ 算法复杂度为
$\Theta(n^2)$
当代价为该段物品的价格之和时,可以用单调队列优化解决。但是当代价为该段物品的价格之和的平方,即
$dp[i]=\min(\max)\left\{dp[j]+(sum[i]-sum[j])^2\right\}$
此时单调队列不可维护,此时考虑斜率优化。设 $\exists k(j>k)$
使得转移更优。那么可得
$dp[j]+(sum[i]-sum[j])^2<dp[k]+(sum[i]-sum[k])^2$ 展开整理,得
$dp[j]-dp[k]+sum[j]^2-sum[k]^2<2\cdot sum[i]\cdot (sum[j]-sum[k])$
再次整理,将其化为分式
$\frac{dp[j]-dp[k]+sum[j]^2-sum[k]^2}{sum[j]-sum[k]}<2\cdot sum[i]$ 令
$f(x)=dp[x]+sum[x]^2$ 可得 $\frac{f(j)-f(k)}{sum[j]-sum[k]}<2\cdot sum[i]$
观察这个式子,发现其很像斜率,在空间中绘出点 $(sum[x],f(x))$
,可以发现转移的最优的点始终在一个下凸壳上,用数据结构维护即可。